package LeetCode1;

/**
 * 验证二叉搜索树
 *
 * @author 是阿秋啊
 * @date 2022/03/28 16:25
 **/
public class Num98 {
    // 方法一，递归访问左右子树
//    public boolean isValidBST(TreeNode root) {
//        return isValidBSTRoot(root, Long.MIN_VALUE, Long.MAX_VALUE);
//    }
//    // lower是用来记录当向右子树访问时的父节点值
      // upper是用来记录当向左子树访问时的父节点值
//    private boolean isValidBSTRoot(TreeNode root, long lower, long upper) {
//        if (root == null) {
//            return true;
//        }
//        if (root.val <= lower || root.val >= upper) {
//            return false;
//        }
//        return isValidBSTRoot(root.left, lower, root.val) && isValidBSTRoot(root.right, root.val, upper);
//    }
    // 方法二，中序遍历
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        // pre在进入左树时代表的是当前节点的左子树
        // pre在进入右树时代表的时当前节点的父节点
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}
